package 算法.leetcode.bytedance;

/**
 * @author lchenglong
 * @date 2022/5/6
 */
public class OfferString_III {

    public static void main(String[] args) {
        OfferString_III instance = new OfferString_III();
        String s1 = "ab";
        String s2 = "eidbaooo";
        boolean ans = instance.checkInclusion(s1, s2);
        System.out.println(ans);
    }
    public boolean checkInclusion(String s1, String s2) {
        // 边界条件
        if (s2 == null ||s1==null||s2.length()==0||s1.length()>s2.length())return false;
        // 欠账表
        int[] cnt = new int[26];
        for (int i=0;i<s1.length();i++) {
            --cnt[s1.charAt(i)-'a'];
        }
        int l = 0,r=0;
        // 保证在[l,r]这个区间内,s2每个字符的个数等于s1的每个字符的个数
       for (;r<s2.length();r++){
           int x = s2.charAt(r)-'a';
           ++cnt[x];
           while (cnt[x]>0){
               // 拆了东墙补西墙
               --cnt[s2.charAt(l)-'a'];
               ++l;
           }
           // 全部还完
           if (r-l+1==s1.length())return true;
       }
        return false;
    }
}
